# grid = [[1,2,3],[4,5,6],[7,8,9]]
# grid=[[-73,61,43,-48,-36],[3,30,27,57,10],[96,-76,84,59,-15],[5,-49,76,31,-7],[97,91,61,-46,67]]
grid=[[50,-18,-38,39,-20,-37,-61,72,22,79],[82,26,30,-96,-1,28,87,94,34,-89],[55,-50,20,76,-50,59,-58,85,83,-83],[39,65,-68,89,-62,-53,74,2,-70,-90],[1,57,-70,83,-91,-32,-13,49,-11,58],[-55,83,60,-12,-90,-37,-36,-27,-19,-6],[76,-53,78,90,70,62,-81,-94,-32,-57],[-32,-85,81,25,80,90,-24,10,27,-55],[39,54,39,34,-45,17,-2,-61,-81,85],[-77,65,76,92,21,68,78,-13,39,22]]
def minFallingPathSum(grid):
    grid_row=len(grid)
    grid_col=len(grid[0])
    if grid_col==1 and grid_row==1:
        #如果只有一列，就直接返回0
        return grid[0][0]
    dp=[[0 for _ in range(grid_col)] for _ in range(grid_row)]
    for i in range(grid_row):
        for j in range(grid_col):
            if i==0:
                dp[i][j]=grid[i][j]
            # if j==0 and j<grid_col-1:
            #     dp[i][j]=dp[i-1][j+1]+grid[i][j]
            # if j>0 and j<grid_col-1:
            #     dp[i][j]=min(dp[i-1][j+1],dp[i-1][j-1])+grid[i][j]
            # if j==grid_col-1:
            #     dp[i][j]=dp[i-1][j-1]+grid[i][j]
            else:
                #除了第一行之外的其他行
                dp[i][j]=min(dp[i-1][:j]+dp[i-1][j+1:])+grid[i][j]
    print(dp)
    print(min(dp[grid_col-1]))

#方法2：方法1的优化,降低一个数量级的时间复杂度
def minFallingPathSum2(grid):
    grid_row=len(grid)
    grid_col=len(grid[0])
    if grid_col==1 and grid_row==1:
        #如果只有一列，就直接返回0
        return grid[0][0]
    dp=[[0 for _ in range(grid_col)] for _ in range(grid_row)]
    i1,i2=-1,-1
    for i in range(grid_row):
        m_index, n_index = -1, -1
        print(i1, i2)
        for j in range(grid_col):
            if i==0:
                dp[i][j]=grid[i][j]
            else:
                #除了第一行之外的其他行
                # dp[i][j]=min(dp[i-1][:j]+dp[i-1][j+1:])+grid[i][j]
                if j==i1:
                    dp[i][j]=dp[i-1][i2]+grid[i][j]
                else:
                    dp[i][j]=dp[i-1][i1]+grid[i][j]
            if m_index==-1:
                m_index=j
            else:
                if dp[i][m_index] > dp[i][j]:
                    if n_index==-1 or dp[i][n_index]>dp[i][m_index]:
                        n_index=m_index
                    m_index=j
                elif dp[i][n_index]>dp[i][j] or n_index==-1:
                    n_index=j
        print("min_value:",dp[i][m_index]," sec_min_value:",dp[i][n_index])
        i1,i2=m_index,n_index
    print(dp)
    print(min(dp[grid_col-1]))
minFallingPathSum2(grid)
minFallingPathSum(grid)


# def minFallingPathSum3(grid):
#     grid_row = len(grid)
#     grid_col = len(grid[0])
#     if grid_col == 1 and grid_row == 1:
#         return grid[0][0]
#     dp = [[0 for _ in range(grid_col)] for _ in range(grid_row)]
#     i1, i2 = -1, -1
#     for i in range(grid_row):
#         m_index, n_index = -1, -1
#         for j in range(grid_col):
#             if i == 0:
#                 dp[i][j] = grid[i][j]
#             else:
#                 if j == i1:
#                     dp[i][j] = dp[i - 1][i2] + grid[i][j]
#                 else:
#                     dp[i][j] = dp[i - 1][i1] + grid[i][j]
#             if m_index == -1:
#                 m_index = j
#             else:
#                 if dp[i][m_index] > dp[i][j]:
#                     m_index = j
#                 elif dp[i][n_index] > dp[i][j] or n_index == -1:
#                     n_index = j
#         i1, i2 = m_index, n_index
#     return min(dp[grid_col - 1])
